


This paper introduces a novel methodology to implement question answering systems,
which is difficult to measure by quantitative metrics. However, in this section
we 
%like to 
show that one can easily implement a system that has a
similar quality as a publicly available question answering system
(WolframAlpha).

% Evaluating retrieval systems is not an easy task, because each system meets a
% specific goal, and therefore classic evaluation metrics (such as precision and
% recall) might not be the best ones. Moreover, there is no dataset nor
% goldstandard queries that can be used besides those from TREC evaluation, but
% are not suitable for BI purposes.
% We suggest an evaluation protocol dedicated to BI retrieval systems, which bases
% in our case on a popular dataset available to the public.


\subsection{Evaluation corpus and data set}

ManyEyes\footnote{See~\url{www-958.ibm.com/}.} is a collaborative
platform where users publish datasets and associated visualizations (i.e.
charts).
One of the most popular datasets is from the American Census
Bureau\footnote{\url{http://www.census.gov/main/www/access.html}.}.
We have integrated it in our data warehouse and created
manually the data schemas corresponding to these dataset (using the original terminology).
The corpus of user questions is composed of the titles of the 50 most popular
visualizations having the census dataset as data source in ManyEyes.
Some of these questions are shown in
table~\ref{tab:goldstandard-queries} (see last page).

\begin{table*}[h!tb]
\centering
\begin{tabular}{lllll}\hline
\multicolumn{1}{c}{\textbf{Query}} & 
\multicolumn{1}{c}{\textbf{Updated query}} & &
\multicolumn{1}{c}{\textbf{Entities}} & 
\multicolumn{1}{c}{\textbf{Comment}}\\\hline\hline
State Population Change & & & $\{\textnormal{State, Population change}\}$ &
\\\hline
Home Ownership & Owner-occupied & &
$\{\textnormal{State, Owner-occupied}$ & \multirow{2}{*}{home $\sim$ dwellings}\\
by State & dwellings by state & & $\textnormal{dwellings}\}$ & \\\hline
 USA States information & & & $\{\textnormal{State}\}$ & \\\hline
 Generation Y in  & population by year & &
 \multirow{2}{*}{$\{\textnormal{Year, Population}\}$} &
 \multirow{2}{*}{generation $\sim$ demographic info.}
 \\
 2010 (Ages 10-32) & for ages 10-32\\\hline
 And the whitest name & \multirow{2}{*}{names white percent} & &
 \multirow{2}{*}{$\{\textnormal{Name, White percent}\}$} &
 \multirow{2}{*}{whitest $\sim$ white} \\
 in America is & & & & \\\hline
 40+ Population Projections & & & $\{\textnormal{Age,
 Population}$ & \\
 by Age & & & $\textnormal{projection}\}$ & \\\hline
 Average Time Spent & & & $\{\textnormal{State}, \textnormal{Median travel}$ &
 \\
Commuting by State & & & $\textnormal{time to work}\}$ & \\\hline
Percent Hispanic by State & & & $\{\textnormal{State}, \textnormal{Hispanic
population}\}$ &\\\hline 
%\multirow{5}{*}{Population by ethnicity} & \multirow{5}{*}{population by race}
%& & $\{\textnormal{State}, \textnormal{White race count},$
%& \multirow{5}{*}{ethnicity $\sim$ race*} \\ 
% & & & $\textnormal{Other race count}, \textnormal{American indian}$ & \\
% & & & $\textnormal{Eskimo and Aleut race count},$ &\\
% & & & $\textnormal{Asian and pacific islander race count},$ & \\
% & & & $\textnormal{Black}, \textnormal{race count}\}$ & \\\hline
Change in city \& town & & & \multirow{2}{*}{$\{\textnormal{Town name},
\textnormal{Population change}\}$} & \\
populations & & & & \\\hline
\multirow{2}{*}{Population} & & &$\{\textnormal{State}, \textnormal{County},
\textnormal{Town name},$ & \\
& & & $\textnormal{Population}\}$ & \\\hline
\multirow{2}{*}{Domestic Net Migration} & & & $\{\textnormal{State},
\textnormal{Domestic net}$ & \\
& & & $\textnormal{migration}\}$  & \\\hline
 Population (by County) & & & $\{\textnormal{County}, \textnormal{Population}\}$
 & \\\hline 
 US surnames & US names & & $\{\textnormal{Count}, \textnormal{Name}\}$ &
 surnames $\sim$ names \\\hline Age distribution  & & & $\{\textnormal{Age},
 \textnormal{Male number},$ & \\
by US population & & & $\textnormal{Female number}\}$ & \\\hline
\multirow{2}{*}{Where are rich people?} & highest  &
& $\{\textnormal{State}, \textnormal{Average household income},$ &
\multirow{2}{*}{rich $\sim$
 household income} \\
 &  household income %per state 
 & & $\textnormal{Median household income}\}$ & \\\hline 
 People covered and not covered & & & $\{\textnormal{State}, \textnormal{Covered}\}$ & \\
by Health Insurance by State & & & $\textnormal{Not covered}\}$ & \\\hline
Southeast Asian American & & & $\{\textnormal{County}, \textnormal{Asian and
Pacific}$ & \\
Population by US County & & & $\textnormal{islander race count}\}$ & \\\hline
%Black vs. white college  & & & 
%$\{\textnormal{State}, \textnormal{Percent white males with at least}$ & \\
%experience percentage  & & & $\textnormal{some college, Percent black
%males with}$ &
%\\
%by state & & & $\textnormal{at least some college}\}$ & \\\hline
Dirtiest states from  & Plant name and  &
&$\{\textnormal{State}, \textnormal{Carbon dioxide}$ & \multirow{2}{*}{dirtiest
$\sim$ emissions} \\
coal pollution & carbon dioxide emissions & & $\textnormal{emissions}\}$ &
 \\\hline \multirow{2}{*}{50MW+ Power Plants} & Plant name with nameplate & &
\{Plant name, & \multirow{2}{*}{500MW+ $\sim$ nameplate capacity} \\
 &  capacity $>$ 500MW & & Nameplate capacity\}& \\\hline
Emissions Per State & & &
$\{\textnormal{State},\textnormal{Methane emissions},\textnormal{Nitrogen}$ & \\
Per Capita & & & $\textnormal{oxide emissions},\textnormal{Mercury emissions}\}$
& \\\hline US Violent Crime & & & $\{\textnormal{Crime rate}\}$ & \\\hline
Deaths per Year & & &
\multirow{2}{*}{$\{\textnormal{Cause}, \textnormal{Per year}\}$} & \\
in the United States & & & & \\\hline
Home Valuation of & & & $\{\textnormal{City},\textnormal{Min valuation},$ & \\
Major Cities in US & & & $\textnormal{Max valuation}\}$ & \\\hline
of Americans without & Americans not covered & &
\multirow{2}{*}{$\{\textnormal{Sate},\textnormal{Without health insurance}\}$} &
\multirow{2}{*}{health insurance $\sim$ covered}\\
health insurance & per state & & & \\\hline
Percent of men in Mass.,  & & & \multirow{2}{*}{$\{\textnormal{Percent men}\}$} & \\
15 and over, never married & & & & \\\hline
Marriages in the United States & & &
$\{\textnormal{State},\textnormal{Marriage rage per}$ & \\
per 1,000 women by state & & & $\textnormal{1,000 women}\}$ & \\\hline
Percentage of population  & & & $\{\textnormal{County}, \textnormal{Percent
population}$ & \\
aged 85+, by county & & & $\textnormal{aged 85+}\}$ & \\\hline
Population by Age & Estimate by age & &
$\{\textnormal{Age},\textnormal{Population estimate}\}$ & population $\sim$
numeric estimate \\\hline 
Civilians Employed  & \multirow{2}{*}{Amount by category} & &
\multirow{2}{*}{$\{\textnormal{Occupation category}\}$} &
\multirow{2}{*}{occupation $\sim$ category} \\
by Occupation & & & & \\\hline
Percent of Population  & & &
$\{\textnormal{State},\textnormal{Percent population}$ & \\
18+ (by state) & & & $\textnormal{of age 18+}\}$ & \\\hline
Population categorized & Population categorized & &
\multirow{2}{*}{$\{\textnormal{Age},\textnormal{Population}\}$} &
\multirow{2}{*}{areas $\sim$ states}
\\
by ages and areas & by ages and states & & & \\\hline 
\end{tabular}
\caption{Excerpt from evaluation corpus. The symbol `$\sim$' indicates how
linguistic resources could improve  %coverage of the current system.
 performances}
\label{tab:goldstandard-queries}
\vspace{-0.8cm}
\end{table*}


%\subsection{Gold standard queries}
%\label{sec:evaluation-goldstandard}
%In~\cite{blunschi2012}: definition of handwritten gold standard queries,
%computation of recall and precision; definition of the ``query complexity''
%(what operations are needed; what execution time does it require?). 

% 
% 
% 
% \subsection{Performance}
% \label{sec:evaluation-performance}
% We have measured the processing time of the overall answering system (see
% Figure~\ref{fig:evaluation-processing-time}).
% On this figure, we represent the processing time before rendering the charts
% (plots ``*'') and after rendering the charts (plots ``x'').
% 
% \begin{figure}[!h]
% \centering
% \begin{tikzpicture}
%     \begin{axis}[width=\linewidth,xlabel=input nodes count,
%         ylabel={processing time (ms)},axis y
%         line*=left,ymin=10000,ymax=15000,legend pos=north west]
%         \addplot[smooth,mark=*,style=dotted] plot coordinates { 
%         (11203,11203)
%         (11655,11655) (12137,12137)
% 		(12615,12615)
% 		(13018,13018)
%     };
%     \legend{before chart generation}
%     \end{axis}
%   
%   \begin{axis}[width=\linewidth,axis y
%   line=right,ymin=0,ymax=5000000,grid=both, legend pos=south east]
%     \addplot[smooth,mark=x]
%         plot coordinates {
%    		(11203,2470619)
% 		(11655,2972001)
% 		(12137,3472285)
% 		(12615,3976904)
% 		(13018,4477776)
%         };
%         \legend{after chart generation}
%   \end{axis}
%   
%     \end{tikzpicture}
% \caption{Processing time before and
% after the chart generation process as
% a function of the schema input nodes
% count}

% \label{fig:evaluation-processing-time}
% \end{figure}
% On this figure, we see that as expected the processing time seems to be a
% proportion of the size of the graph used as input of the pattern matching
% algorithm. 
% The part of the execution time dedicated to rendering the chart is
% approximatively a third of the global execution time.
% This is due to the fact that datasets  that are rendered as charts are too
% valuminous.

\subsection{Results}




% Recall is not a metrics of interest in our case, because the goldstandard
% queries correspond to exactly one chart, i.e. one database query.
For determining the performance of our question answering system (\textsc{Quasl}),
we use the measure \emph{success at k} that indicates at which position $k$
the relavant result (i.e. chart) occurs in average within the list of results. 
%
Figure~\ref{fig:success-k-1} compares the success for $k=1$ 
(on the left) to $k=10$ (on the right) for \textsc{Quasl} and WolframAlpha.
The results for \emph{updated questions} stands for results 
where the questions has been modified in
such a way that the system can better respond (see also table~\ref{tab:goldstandard-queries}). 
For instance, we have observed that WolframAlpha provides better results if
some questions are prefixed or suffixed with ``US'' or ``Census'' to explicit a
restriction to a subset of available data (``US'') or to the dataset itself
(``Census''). Other questions have been rephrased (e.g., ``Where are the rich people''
to ``highest houshold income'') to give the systems a chance to answer them as well.
Thus the results for \emph{updated questions} show the
assumed performance when optimizing both systems with respect to the type of questions 
in the \emph{gold standard} and the data set. 

Given the \emph{gold standard's} questions, our system outperforms WolframAlpha by far.
However, we observed that WolframAlpha seems to include only a fraction of the Census data set.
Therefore, we computed a second plot (see figure~\ref{fig:success-k-2}), which 
ignores all questions that could not be answered by WolframAlpha 
(assuming that the correpsonding data was not available to the system). 
Beforehand, we tried to reformulate the questions several times to 
ensure that the data is indeed unknown.
%
The results in figure~\ref{fig:success-k-2} show that our system still performs 
better up to $k\leq4$ and that the performance of WolframAlpha is superior to 
the one of \textsc{Quasl} for $k>4$ (under the assumption presented above). 
Thus, we can assume overall a more less similar performance of both systems.


%This can be explained by the fact that WolframAlpha has a better average
%precision than \textsc{Quasl} (see
%table~\ref{tab:evaluation-average-precision}).
%\begin{table}[h]
%\centering
%\begin{tabular}{ll}\hline
%\multicolumn{1}{c}{\textbf{\textsc{Quasl}}} &
%\multicolumn{1}{c}{\textbf{WolframAlpha}}\\\hline\hline
%$0.26$ & $0.43$\\\hline
%\end{tabular}
%\caption{Average precisions of \textsc{Quasl} and WolframAlpha}
%\label{tab:evaluation-average-precision}
%\end{table}
%Table~\ref{tab:evaluation-average-precision},
%values have been computed based on
%the gold-standard queries.
%The definition of average precision can
%be found in~\cite{Moffat:2008:RPM:1416950.1416952}.


% It would be great to lead some user satisfaction evaluation.
% We present figure~\ref{fig:html5} a screenshot of the result page for the query
% ``Revenue per store in New York''.
% \subsection{User experience}
% \begin{figure}[!h]
% \centering
% \includegraphics[width=5cm]{img/screenshot-1}
% \label{fig:html5}
% \caption{HTML5 result page for the query ``Revenue per store in New York''}
% \end{figure}
% Figure~\ref{fig:iphone} is a screenshot of the iPhone app that we have
% implemented, and that implements a siri-like support for three languages
% (English, German and French).
%  \begin{figure}[!h]
% \centering
% \includegraphics[width=5cm]{img/screenshot-2}
% \label{fig:iphone}
% \caption{iPhone app with Siri-like support}
% \end{figure}

% learning of the evaluation

\subsection{Discussion}
Our experiment shows that \textsc{Quasl} behaves to some extend 
similarly as WolframAlpha, which is a well-proven system.
However, in the follwing we like to discuss optimizations that 
would further improve our performance for the given questions.
The second column of table~\ref{tab:goldstandard-queries} 
(``updated question'') depicts modification 
required for the system to correctly interpret users' requests. 
In the last column (``comment'') we provide a brief explanation on how the
system could be easily improved in order to correctly interpret users' initial
requests. 

For instance, the second question ``Home ownership by State'' fails, because the
term `ownership' is not part of the terminology of the data warehouse; 
but the term `dewllings' appears in some measures. Thus, basic linguistic
resources (like WordNet) could be used to relate synonyms or terms with similar
meanings. 
The fifth question (``And the whitest name in America is'') also requires little
effort to be understood by the system: the base form of the word
`whitest' is `white' (which is known to the system). Thus adding a stemming
component would lead to an
%successful 
answered question in that case.

An interesting question is ``Where are rich people?''. It would require 
a little more effort in order to be correctly processed by
\textsc{Quasl}. To answer this question, it requires to attach additional
semantics to the data warhouse to determine locations that would be recognized
by the term `where'. In addition, one would configure a range filter (e.g, using
natural language patterns) to declare the meaning of `rich' (i.e. a certain income 
range). The question ``of Americans covered by health insurance'' is of similar kind, 
because the term ``cover'' can be translated to a filter on the fact table for  
``health insurance''. The question ``500MW+ Power Plants'' would need a special
natural language pattern to parse ``500MW+''.








